package com.estudy.array;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author tim.xie
 * @date 2022/6/30 14:36
 * @description 217. 存在重复元素 https://leetcode.cn/problems/contains-duplicate/
 * 数据结构 数组 简单
 * 哈希表 排序
 */
public class ContainsDuplicate {

    /**
     * 数组中的每个元素都插入到哈希表中
     * 如果插入一个元素时发现该元素已经存在于哈希表中
     * 则说明存在重复元素
     * @param nums
     * @return
     */
    public boolean containsDuplicateHash(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for(int num : nums) {
            if (!hashSet.add(num)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 数组排序之后,重复的元素一定在相邻位置
     * @param nums
     * @return
     */
    public boolean containsDuplicateSort(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length -1; i++) {
            if (nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }

    @Test
    public void test() {
        System.out.println(containsDuplicateHash(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 1}));
        System.out.println(containsDuplicateSort(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 1}));
    }

}
